class Solution
{
public:
    int minFlips(vector<vector<int>> &mat)
    {
        return dfs(mat, 0, 0);
    }

    int dfs(vector<vector<int>> &mat, int m, int n)
    {
        // 遍历到最后一个元素时，检查所有元素
        if (m == mat.size() - 1 && n == mat[0].size() - 1)
        {
            int lastReverse = 0;
            if (mat[m][n] != 0)
            {
                reverseAt(mat, m, n);
                lastReverse = 1;
            }
            for (auto &row : mat)
            {
                for (auto &num : row)
                {
                    if (num != 0)
                    {
                        if (lastReverse)
                        {
                            reverseAt(mat, m, n);
                        }
                        return -1;
                    }
                }
            }
            if (lastReverse)
            {
                reverseAt(mat, m, n);
            }
            return lastReverse;
        }

        // 修改或不修改当前元素，分别递归下去
        // 修改后，还要改回来
        int nextN = (n + 1) % mat[0].size();
        int nextM = m + (n + 1) / mat[0].size();
        int nonChangeResult = dfs(mat, nextM, nextN);
        reverseAt(mat, m, n);
        int changeResult = dfs(mat, nextM, nextN);
        reverseAt(mat, m, n);
        if (nonChangeResult == -1 && changeResult == -1)
        {
            return -1;
        }
        else if (changeResult == -1)
        {
            return nonChangeResult;
        }
        else if (nonChangeResult == -1)
        {
            return changeResult + 1;
        }
        else
        {
            return min(changeResult + 1, nonChangeResult);
        }
    }

    void reverseAt(vector<vector<int>> &mat, int m, int n)
    {
        mat[m][n] = !mat[m][n];
        if (m > 0)
        {
            mat[m - 1][n] = !mat[m - 1][n];
        }
        if (n > 0)
        {
            mat[m][n - 1] = !mat[m][n - 1];
        }
        if (m < mat.size() - 1)
        {
            mat[m + 1][n] = !mat[m + 1][n];
        }
        if (n < mat[0].size() - 1)
        {
            mat[m][n + 1] = !mat[m][n + 1];
        }
    }
};